import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution437 {

    int res = 0;

    int doCompute(List<Integer> path, int target){
        int count = 0;
        int sum = 0;
        for (int i = path.size()-1; i >= 0 ; i--) {
            sum += path.get(i);
            if(sum == target){
                count++;
            }
        }
        return count;
    }

    void travelDFS(TreeNode tmpNode, List<Integer> path, int target){
        if(tmpNode == null){
            return;
        }
        path.add(tmpNode.val);
        res += doCompute(path, target);
        travelDFS(tmpNode.left, path, target);
        travelDFS(tmpNode.right, path, target);
        path.remove(path.size()-1);
    }

    public int pathSum(TreeNode root, int targetSum) {
        travelDFS(root, new ArrayList<>(), targetSum);
        return res;
    }
}
